package datastruct;


import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists {

    /**
     * LeetCode T23 合并K个升序链表
     * @param args
     */
    public static void main(String[] args) {


    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0){
            return null;
        }
        ListNode head = new ListNode(0, null);
        ListNode tail = head;
        PriorityQueue<Status> queue = new PriorityQueue<>(new Comparator<Status>() {
            @Override
            public int compare(Status o1, Status o2) {
                return o1.value - o2.value;
            }
        });
        //对优先队列进行初始化
        for (int i = 0; i < lists.length; i++){
            if (lists[i] != null){
                queue.offer(new Status(lists[i].val, lists[i]));
            }
        }
        while (!queue.isEmpty()){
            Status status = queue.poll();
            tail.next = status.ptr;
            tail = tail.next;
            if (status.ptr.next != null){
                queue.offer(new Status(status.ptr.next.val, status.ptr.next));
            }
        }

        return head.next;

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Status implements Comparable<Status>{
    int value;
    ListNode ptr;
    Status(){}

    Status(int value, int ptr){
        this.value = value;
    }

    public Status(int value, ListNode list) {
        this.value = value;
        this.ptr = list;
    }

    @Override
    public int compareTo(Status o) {
        return this.value - o.value;
    }
}

